package com.u17;

import java.util.ArrayList;

/**
 * @author u17
 * https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
 */
public class Solution {

    /**
     * 借用数组
     * @param nums
     * @return
     */
    public int removeDuplicates(int[] nums) {
        ArrayList<Integer> integers = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (integers.contains(nums[i])) {
                continue;
            }
            integers.add(nums[i]);
        }
        for (int i = 0; i < integers.size(); i++) {
            nums[i] = integers.get(i);
        }
        return nums.length;
    }

    /**
     * 使用原数组进行修改(快慢指针)
     * @param nums
     * @return
     */
    public int removeDuplicates2(int[] nums) {

        int n = nums.length;

        int fast = 1;

        int low = 1;

        while (fast < n) {
            if (nums[fast] != nums[fast - 1]) {
                nums[low++] = nums[fast];
            }
            fast++;
        }
        return low;
    }

    /**
     * 改进的代码
     * @param nums
     * @return
     */
    public int removeDuplicates3(int[] nums) {

        int n = 0;

        for (int j = 1; j < nums.length; j++) {
            if (nums[n] != nums[j]) {
                // ++n 表示当前遍历到的数覆盖++n上的数
                nums[++n] = nums[j];
            }
        }

        return ++n;
    }




    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = new int[]{0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
        System.out.println(solution.removeDuplicates3(nums));
    }
}
